#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<string> res;
		string out = "";
		dfs(n, 0, 0, out, res);
		return res;
	}
	void dfs(int n, int left, int right, string &out, vector<string> &res) {
		if (left < n) {
			out.push_back('(');
			dfs(n, left + 1, right, out, res);
			out.pop_back();
		}
		if (right < left) {
			out.push_back(')');
			dfs(n, left, right + 1, out, res);
			out.pop_back();
		}
		if (out.size() == n * 2)
			res.push_back(out);
	}
};

int main() {

	Solution* su = new Solution();
	vector<string> strs = su->generateParenthesis(3);
	for (vector<string>::iterator iter = strs.begin(); iter != strs.end(); ++iter) {
		cout << *iter << endl;
	}
	return 0;
}